package codetop.dp;

import java.util.Arrays;

public class Code322 {
    public int coinChange(int[] coins, int amount) {
        int []dp=new int[amount+1];
        Arrays.sort(coins);
        for (int i = 1; i <dp.length ; i++) {
            int min=-1;
            for (int j = 0; j < coins.length; j++) {
                int coin=coins[j];
                if (i>=coin&&dp[i-coin]!=-1){
                    if (min==-1){

                        min=dp[i-coin]+1;
                    }
                    else {

                        min=Math.min(min,dp[i-coin]+1);
                    }

                }
            }
            dp[i]=min;
        }
        return dp[amount];
    }
}
